//最后一块石头的重量II
class Solution {
public:
    int lastStoneWeightII(vector<int>& stones) {
        int sum = 0;
        for(auto& x : stones) sum += x;
        int m = stones.size();

        vector<int> dp(sum/2+1);
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(int j = sum/2 ; j >= 0 ; --j)
            {
                if(j >= stones[i-1] && dp[j-stones[i-1]] + stones[i-1] > dp[j]) dp[j] = dp[j-stones[i-1]] + stones[i-1];
            }
        }
        return sum - 2 * dp[sum/2] ;
    }
};

//完全背包
class Solution {
  public:
    int Solution1(int v, int n, vector<vector<int> >& nums)
    {
        //第一题：求这个背包至多能装多大价值的物品？
        vector<int> dp(v + 1);
        int m = nums.size();
        for (size_t i = 1 ; i <= m ; ++i) {
            for (int j = 0 ; j <= v ; ++j) {
                if (j >= nums[i - 1][0] && dp[j - nums[i - 1][0]] + nums[i - 1][1] > dp[j])
                        dp[j] = dp[j - nums[i - 1][0]] + nums[i - 1][1];
            }
        }
        return dp[v];
    }
    int Solution2(int v, int n, vector<vector<int> >& nums)
    {
        //第二题：若背包恰好装满，求至多能装多大价值的物品？
        vector<int> dp(v+1,-1);
        int m = nums.size();
        dp[0] = 0;
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(int j = 0 ; j <= v ; ++j)
            {
                if(j >= nums[i-1][0] && dp[j-nums[i-1][0]] != -1 && dp[j-nums[i-1][0]] + nums[i-1][1] > dp[j]) dp[j] = dp[j-nums[i-1][0]] + nums[i-1][1];
            }
        }
        return dp[v];
    }
    vector<int> knapsack(int v, int n, vector<vector<int> >& nums) {
        int val1 = Solution1(v,n,nums);
        int val2 = Solution2(v,n,nums);
        if(val2 == -1) return {val1,0};
        else return {val1,val2};
    }
};

//零钱兑换
class Solution {
public:
    int coinChange(vector<int>& nums, int amount) {
        int m = nums.size();
        vector<int> dp(amount+1,-1);
        dp[0] = 0;
        for(size_t i = 0 ; i < m ; ++i)
        {
            for(int j = 0 ; j <= amount ; ++j)
            {
                if(j >= nums[i] && dp[j-nums[i]] != -1 && (dp[j] == -1 || dp[j-nums[i]]+1 < dp[j])) dp[j] = dp[j-nums[i]] + 1;
            }
        }
        return dp[amount];
    }
};

//零钱兑换II
class Solution {
public:
    int change(int amount, vector<int>& nums) {
        int m = nums.size();
        vector<long long> dp(amount+1,-1);
        dp[0] = 1;
        for(size_t i = 1 ; i <= m ; ++i)
        {
            for(int j = 1 ; j <= amount ; ++j)
            {   
                int val1 = 0 , val2 = 0;
                if(dp[j] != -1) val1 = dp[j];
                if(j >= nums[i-1] && dp[j-nums[i-1]] != -1) val2 = dp[j-nums[i-1]];
                if(val1 != -1 || val2 != -1) dp[j] = static_cast<long long>(val1) + val2;
                else dp[j] = -1;
            }
        }
        if(dp[amount] == -1) return 0;
        else return dp[amount];
    }
};

//完全平方数
class Solution {
public:
    int numSquares(int n) {
        vector<int> nums;
        int i = 1;
        while (i * i <= n) {
            nums.push_back(i * i);
            i++;
        }

        vector<int> dp(n + 1,0x3f3f3f3f);
        dp[0] = 0;
        for (size_t i = 0; i < nums.size(); ++i) 
        {
            for (size_t j = 0;  j <= n; ++j) 
            {
                if(j >= nums[i] && dp[j-nums[i]]+1 < dp[j]) dp[j] = dp[j-nums[i]]+1;
            }
        }
        return dp[n];
    }
};